package PrefixSum$DoublePointer;

/**
 * 最大子数组和
 * https://leetcode-cn.com/problems/maximum-subarray/
 * 前缀和数组S S[i] = S[i - 1] + A[i]
 * 子段和 sum(i, j) = S[j] - S[i - 1]  [i, j]是闭区间
 */
public class MaximumSubarray {
    /**
     * 解法一：该题要求最大子段和，也就是在计算出前缀和的基础上，控制住右端j，找到左端i， 使得sum(i, j)最大
     * 计算前缀和时间复杂度O(n)，找到sum(i, j)最大的 i 和 j 需要O(n^2)
     * 换一种思路，sum(i, j) = S[j] - S[i - 1]，j是固定的，那么只需要S[i -1]是最小的就可以了
     * 所以在计算前缀和的时候，同时维护一个数组，记录该位置左侧前缀和最小的值
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        int[] prefixSumMin = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++){
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1]; // 计算前缀和
            prefixSumMin[i] = Math.min(prefixSumMin[i - 1], prefixSum[i]); // 计算i位置左侧所有前缀和中，最小的前缀和
        }
        int maxSum = prefixSum[1];
        for (int i = 1; i <= nums.length; i++)
            maxSum = Math.max(maxSum, prefixSum[i] - prefixSumMin[i - 1]);
        return maxSum;
    }

    /**
     * 解法二：贪心计算，当一个子段的和加上新的元素整体变小的时候，说明这个子段到了尽头，需要开启新的子段，新元素就是新子段的左边端点
     * 当一个字段和加上新的元素整体变大的时候，将新元素加入该字段
     * @param nums
     * @return
     */
    public int maxSubArrayII(int[] nums){
        int sum = 0; // 初始子段和为零
        int max = nums[0]; // 取第一个元素为初始最大值

        for (int num : nums){
            sum = Math.max(sum + num, num);
            max = Math.max(max, sum);
        }
        return max;
    }
}
